/*
这是一个用链表实现的队列,该栈接受的数据类型通过头文件修改
所有进出队列的数据需要先进行空指针检查,不能使用非指针类型
*/

#include "link_queue_simple.h"
#include "stdio.h"
#include "stdlib.h"

// 队列节点
struct node {
  Item data;
  struct node *next;
};

// 队列结构
struct queue_t {
  struct node *head;
  struct node *last;
  size_t size;
};

cqueue queue_create(void) {
  cqueue q;
  if ((q = malloc(sizeof(struct queue_t))) == NULL)
    return NULL;

  //队列结构有头和尾尾指针,不需要空链表头
  q->last = q->head = NULL;
  q->size = 0;

  return q;
}

bool queue_append(cqueue q, Item data) {
  struct node *pnode = malloc(sizeof(struct node));
  if (pnode == NULL)
    return false;

  pnode->data = data;
  pnode->next = NULL;

  if (q->head == NULL && q->last == NULL)
    q->head = q->last = pnode;
  else {
    q->last->next = pnode;
    q->last = pnode;
  }

  ++q->size;
  return true;
}

void queue_destory(cqueue q) {
  queue_clear(q);
  free(q);
}

void queue_clear(cqueue q) {
  struct node *cur_node;
  while (q->head) {
    cur_node = q->head;
    q->head = cur_node->next;
    free(cur_node);
  }
  // 不要忘记设置last指针
  q->last = NULL;
}

Item queue_remove_head(cqueue q) {
  struct node *phead = q->head;
  Item data = phead->data;

  // 仅有一个元素的情况,很重要
  if (q->head == q->last)
    q->last = NULL;

  q->head = phead->next;
  free(phead);

  --q->size;
  return data;
}

Item queue_head(cqueue q) { return q->head->data; }

Item queue_last(cqueue q) { return q->last->data; }

bool queue_is_empty(cqueue q) { return q->size == 0; }

bool queue_is_full(cqueue q) { return false; }

size_t queue_length(cqueue q) { return q->size; }
